package class07;

import utils.TreeNode;

/**
 * @Description: Code04_路径和
 * https://leetcode.com/problems/path-sum
 */
public class Code04_路径和 {

    public static boolean isSum = false;

    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        isSum = false;
        process(root, 0, targetSum);
        return isSum;
    }

    public static void process(TreeNode x, int preSum, int targetSum) {
        //没有子节点了  是最终的叶子节点 计算最终结果
        if (x.left == null && x.right == null) {
            if (x.val + preSum == targetSum) {
                isSum = true;
            }
            return;
        }
        // x是非叶节点
        preSum += x.val;
        if (x.left != null) {
            process(x.left, preSum, targetSum);
        }
        if (x.right != null) {
            process(x.right, preSum, targetSum);
        }
    }

    public static void main(String[] args) {
        TreeNode n41 = new TreeNode(7);
        TreeNode n42 = new TreeNode(2);
        TreeNode n43 = new TreeNode(1);
        TreeNode n31 = new TreeNode(11, n41, n42);
        TreeNode n32 = new TreeNode(13);
        TreeNode n33 = new TreeNode(4, null, n43);
        TreeNode n21 = new TreeNode(4, n31, null);
        TreeNode n22 = new TreeNode(8, n32, n33);
        TreeNode n11 = new TreeNode(5, n21, n22);

        boolean b = hasPathSum(n11, 18);
        System.out.println(b);
    }
}
